package search;

public class BinarySearch {

    /** 二分法查找
     * 1. 前提： 有已排序数据A
     * 2. 定义左边界L, 右边界 R, 确定搜索范围，循环执行二分法查找
     * 3. 获取中间索引 M = Floor(L+R)/2
     * 4. 中间索引的值 A[M] 与目标值 T 进行比较
     * 5.   ① A[M] = T 表示找到，返回中间的索引
     *      ② A[M] > T,中间值右侧的其他元素都大于T，无需比较，中间索引左边去找，M-1 设置为右边界，重新查找
     *      ③ A[M] < T, 中间值左侧的其他元素都小于T，无需比较，中间索引右边去找，M+1设置为左边界，重新查找
     */

    public static void main(String[] args) {
        Integer [] array = {1,2,3,4,5,6,7,8,60,61,70,80,85,95,100};
        int target = 95;
        int index = getIndex(array, target);
        System.out.printf("index:"+ index +",value:");
    }

    private static int getIndex(Integer [] array,int target){
        int L = 0;
        int R = array.length -1;
        while (L <= R){
            int M = (L+R) / 2; // 溢出问题，  L/2 + R/2  ==> L - L/2 + R/2 ==> L + (R/2-L/2) ==> L + (R-L)/2
            if (array[M] == target){
                return M;
            }else if (array[M] > target){
                R = M -1;
            }else {
                L = M + 1;
            }
        }
        return -1;
    }



}
